package wtx.leetcode;

/**
 * Given an array nums of n integers where n > 1, return an array output such
 * that output[i] is equal to the product of all the elements of nums except
 * nums[i]. Example:
 * 
 * Input: [1,2,3,4] Output: [24,12,8,6]  
 * Note: Please solve it without division and in O(n).
 * [1,  1,  2, 6]
 * [24, 12, 4, 1]
 */
public final class Solution {

  public int[] productExceptSelf(int[] nums) {
    if (nums == null || nums.length < 2) {
      return null;
    }
    int[] ret = new int[nums.length];
    // O(3n)
    int[] forward = new int[nums.length];
    forward[0] = 1;
    for (int i = 1; i < nums.length; ++i) {
      forward[i] = nums[i-1] * forward[i-1];
    }
    ret[nums.length-1] = 1;
    for (int i = nums.length-2; i >= 0; --i) {
      ret[i] = nums[i+1] * ret[i+1];
    }

    for (int i = 0; i < nums.length; ++i) {
      ret[i] *= forward[i];
    }
    return ret;
  }


  public static void main(String[] args) {
    Solution s = new Solution();
    int[] input = {1,2,3,4};
    int[] ret = s.productExceptSelf(input);
    for (int i : ret) {
      System.out.print(String.format("%d, ",i));
    }
    System.out.println();
  }
}
